package com.github.zyf.ioaj.algorithm.evolutionary;

import com.github.zyf.ioaj.algorithm.AbstractAlgorithm;
import com.github.zyf.ioaj.algorithm.Input;
import com.github.zyf.ioaj.algorithm.Output;
import com.github.zyf.ioaj.annotation.internal.Algorithm;
import com.github.zyf.ioaj.annotation.internal.BasicParam;
import com.github.zyf.ioaj.annotation.internal.TempParam;
import com.github.zyf.ioaj.constant.FileType;
import com.github.zyf.ioaj.constant.ParamType;
import com.github.zyf.ioaj.export.*;

import java.util.Arrays;
import java.util.Random;

/**
 * <h1>Genetic Algorithm</h1>
 * <p>遗传算法</p>
 * <p>默认求解最小值，如果需要求解最大值，将目标函数乘以-1即可，最后得到的值再次乘以-1就是得到的最优值（自变量取值不用乘以-1）</p>
 * <p>需要计算则调用{@link #go()}</p>
 * <p>需要跟踪每次迭代则调用{@link #tracker(String, String, String, FileType)}</p>
 * <p>需要生成报告则调用{@link #report(String, String, String, FileType)}</p>
 * <p>
 * 遗传算法借鉴了达尔文的进化论和孟德尔的遗传学说。
 * 其本质是一种并行、高效、全局搜索的方法。
 * 其能够在搜索过程中自动获取和积累搜索空间的知识，并自适应的控制搜索过程以获得最优解。
 * 基本步骤包括：初始化---基因复制---基因交叉---基因变异---基因择优。
 * </p>
 * <p>
 * 遗传算法使用“适者生存”的原则，在潜在的解决方案种群中逐次产生一个近似最优的方案。
 * 在遗传算法的每一代中，根据个体在问题域中的适应度和从自然学说中借鉴来的再造方法进行个体选择，产生一个新的近似解。
 * 在这个过程中导致种群的进化，得到的新个体比原个体更能适应环境，就像自然界中的改造一样。
 * </p>
 * <p>
 * 该算法主要包括四个主要组成部分：
 * <ol>
 *     <li>
 *         编码解码({@link #decode(String[])})：使用二进制进行编码，并利用解码函数将二进制码映射到可行域中。对于不同的问题编码方式会作出相应调整。
 *     </li>
 *     <li>
 *         基因复制({@link #gene_copy()})：为了得到最优解，算法模拟基因编码的复制。
 *         并控制较为优秀的基因要多复制（表现为复制概率更大），而较差一点的基因要少复制（表现为复制概率较小）。
 *         这里的优秀与否取决于对应编码的适应度。
 *     </li>
 *     <li>
 *         基因交叉({@link #gene_cross(String[][])})：使用三段式交叉方式，即掐头，去尾，交换中间。代码中对相邻两编码进行“基因”交叉操作，所交换部分由随机数控制。
 *     </li>
 *     <li>
 *         基因变异({@link #gene_mutation(String[][])})：由于采用二进制编码，因此“基因”变异十分简单，可以描述为：随机选择位点进行取反操作即可，因为二进制串只有0和1。
 *     </li>
 * </ol>
 *
 * @author zyf
 */
@Algorithm
public class GA extends AbstractAlgorithm {

    /**
     * 种群个体个数
     */
    @BasicParam(type = ParamType.INT, desc = "种群个体个数")
    private int n;

    /**
     * 用于编码的串长
     */
    @BasicParam(type = ParamType.INT, desc = "用于编码的串长")
    private int length;

    /**
     * 基因交叉概率
     */
    @TempParam(type = ParamType.DOUBLE, desc = "基因交叉概率")
    private double pc;
    /**
     * 基因变异概率
     */
    @TempParam(type = ParamType.DOUBLE, desc = "基因变异概率")
    private double pm;

    /**
     * 每一个种群当前适应度，double[n]
     */
    @TempParam(type = ParamType.DOUBLE_ARRAY_1, desc = "每一个种群当前适应度")
    private double[] fit;

    /**
     * 每一个种群个体当前的基因，每一行的一个个体的var字符串
     */
    @TempParam(type = ParamType.STRING_ARRAY_2, desc = "每一个种群个体当前的基因")
    private String[][] gene;

    /**
     * 当前种群的最优解
     */
    @TempParam(type = ParamType.DOUBLE_ARRAY_1, desc = "当前种群的最优解")
    private double[] x;

    /**
     * 自变量个数
     */
    private int D;
    /**
     * 自变量取值下限
     */
    private double[] lb;
    /**
     * 自变量取值下限
     */
    private double[] ub;

    /* 初始化部分 */

    /**
     * 抽象算法构造函数，需要提供输入量，即提前初始化好{@link Input}对象
     *
     * @param input {@link Input}
     */
    public GA(Input input) {
        super(input);
        init();
    }

    private void init() {
        this.n = 50;
        this.length = 20;
        this.pc = 0.6;
        this.pm = 0.1;

        this.D = getInput().getVarNum();
        this.lb = getInput().getLb();
        this.ub = getInput().getUb();

        initFit();
        initGene();
        initX();
    }

    private void initFit() {
        fit = new double[n];
        int i;
        for (i = 0; i < n; i++) {
            fit[i] = 0.0;
        }
    }

    private void initGene() {
        gene = new String[n][D];
        int i, j, k;
        for (i = 0; i < n; i++) {
            for (j = 0; j < D; j++) {
                gene[i][j] = Integer.toBinaryString(new Random().nextInt((int) Math.pow(2, length) + 1));
                gene[i][j].substring(2);
                int len = gene[i][j].length();
                if (len < length) {
                    StringBuilder s = new StringBuilder();
                    for (k = 0; k < length - len; k++) {
                        s.append('0');
                    }
                    gene[i][j] = s + gene[i][j];
                }
            }
        }
    }

    private void initX() {
        this.x = new double[D];
        x = decode(gene[0]);
        fit[0] = getInput().getFunction().apply(x);
        int i;
        for (i = 0; i < n; i++) {
            double[] now_x = decode(gene[i]);
            fit[i] = getInput().getFunction().apply(now_x);
            if (fit[i] < getInput().getFunction().apply(x)) {
                x = now_x.clone();
            }
        }
    }

    /* 计算部分 */

    /**
     * 二进制映射十进制
     *
     * @param genes 基因数组（存储内容是二进制）
     * @return 解码后的十进制数组，double[]类型
     */
    private double[] decode(String[] genes) {
        double[] mapped = new double[D];
        int j;
        for (j = 0; j < D; j++) {
            mapped[j] = lb[j] + Integer.parseInt(genes[j], 2) * (ub[j] - lb[j]) / ((int) Math.pow(2, length) - 1);
        }
        return mapped;
    }

    private double min(double[] doubles) {
        double min = doubles[0];
        for (double d : doubles) {
            min = Math.min(d, min);
        }
        return min;
    }

    /**
     * <p>基因复制</p>
     * <p>
     * 举个例子来描述复制过程：假设我们的目标是求最大值，此时适应度即为编码对应的函数值。
     * <ol>
     *     <li>假设：fit(a) = 1，fit(b) = 2，fit(c) = 3，fit(d) = 4</li>
     *     <li>对每个编码适应度进行归一化，即可得到对应的概率P为：P(a) = 1/10, P(b) = 2/10, P(c) = 3/10, P(d) = 4/10</li>
     *     <li>我们将概率进行依次累加得到序列：1/10, 3/10, 6/10, 10/10</li>
     *     <li>
     *         此时我们取一随机数，判断随机数落入区间的情况：
     *         <ul>
     *             <li>r <= 1/10，则编码a需要进行复制</li>
     *             <li>1/10 < r <= 3/10，则编码b需要进行复制</li>
     *             <li>3/10 < r <= 6/10，则编码c需要进行复制</li>
     *             <li>6/10 < r <= 10/10，则编码d需要进行复制</li>
     *         </ul>
     *     </li>
     * </ol>
     * </p>
     *
     * @return 复制后的基因，String[][] 类型
     */
    private String[][] gene_copy() {
        String[][] new_gene = new String[n][D];
        // 计算复制每个个体复制基因的概率， 概率越大复制概率越大
        // 按照取值赋概率， 取值越小概率越大。 因此对所有取值先预处理
        // 预处理首先要非负，因为概率取值原理是归一化
        double min_val = min(fit);
        double add_val;
        // 原值要加上add_val，目的是保证取倒数后分母不能为0
        if (min_val < 0) add_val = -min_val + 1;
        else add_val = 0.0;
        // 之所以取倒数是因为，值越小需要概率越大
        double[] tem = Arrays.stream(fit).map(d -> 1 / (d + add_val)).toArray();
        // 进行求和
        double s_tem = Arrays.stream(tem).sum();
        // 归一化
        double[] p = Arrays.stream(tem).map(d -> d / s_tem).toArray();
        // 概率求和累加（cumulate）, 为了方便让概率大的多复制
        double[] cum_p = new double[n];
        cum_p[0] = p[0];
        int i, j;
        for (i = 1; i < n; i++) {
            cum_p[i] = cum_p[i - 1] + p[i];
        }
        // 制造一组有序的随机数（用于概率选择）， 随机数落入累加区间即需要复制
        double[] choice = new double[n];
        for (i = 0; i < n; i++) {
            choice[i] = Math.random();
        }
        Arrays.stream(choice).sorted();
        i = 0;
        j = 0;
        while (j < n && i < n) {
            // 只要当前随机数小于右端点就说明落入该区间，需要复制
            if (choice[j] <= cum_p[i]) {
                new_gene[j] = gene[i].clone();
                j++;
            } else {
                // 如果随机数大于右端点，需要和之后的区间进行比较
                i++;
            }
        }
        return new_gene;
    }

    /**
     * 基因交叉，按掐头、去尾、交换中间方式交叉
     *
     * @param new_gene 待交叉的新基因
     */
    private void gene_cross(String[][] new_gene) {
        int i = 1, j;
        // 相邻两个个体同种基因（同一自变量编码）进行交叉
        while (i < n) {
            if (Math.random() < pc) {
                // 取出要进行交叉的两个个体
                String[] indiv1 = new_gene[i - 1].clone();
                String[] indiv2 = new_gene[i].clone();
                // 逐变量进行编码交叉
                for (j = 0; j < D; j++) {
                    // 两个划分 h1, h2 的取值范围为 0 ~ length-1
                    int h1 = new Random().nextInt(length);
                    int h2 = new Random().nextInt(length);
                    // 保证有序性
                    if (h1 > h2) {
                        int temp = h1;
                        h1 = h2;
                        h2 = temp;
                    }
                    // 基因交叉
                    new_gene[i - 1][j] = indiv1[j].substring(0, h1) + indiv2[j].substring(h1, h2 + 1) + indiv1[j].substring(h2 + 1);
                    new_gene[i][j] = indiv2[j].substring(0, h1) + indiv1[j].substring(h1, h2 + 1) + indiv2[j].substring(h2 + 1);
                }
            }
            i = i + 2;
        }
    }

    /**
     * 基因变异
     *
     * @param new_gene 待变异的基因
     */
    private void gene_mutation(String[][] new_gene) {
        int i, j, k;
        for (i = 0; i < n; i++) {
            for (j = 0; j < D; j++) {
                while (Math.random() < pm) {
                    // 随机挑选2个数变异，不能变异太多了
                    for (k = 0; k < 2; k++) {
                        // 随机获取要变异的下标
                        int index = new Random().nextInt(length);
                        if (new_gene[i][j].charAt(index) == '0') {
                            new_gene[i][j] = new_gene[i][j].substring(0, index) + '1' + new_gene[i][j].substring(index + 1);
                        } else {
                            new_gene[i][j] = new_gene[i][j].substring(0, index) + '0' + new_gene[i][j].substring(index + 1);
                        }
                    }
                }
            }
        }
    }

    /**
     * 每次迭代时扫描一边
     *
     * @param t 迭代次数
     */
    public void scan(int t) {
        int iter = getIter();
        // 控制交叉概率线性递减 [0.6 - 0.2]
        pc = 0.6 - 0.4 * t / iter;
        // 控制变异概率线性递减 [0.3 - 0.1]
        pm = 0.3 - 0.2 * t / iter;
        String[][] new_gene = gene_copy();
        gene_cross(new_gene);
        gene_mutation(new_gene);
        int i;
        for (i = 0; i < n; i++) {
            double new_fit = getInput().getFunction().apply(decode(new_gene[i]));
            if (new_fit < fit[i]) {
                // 概率保留优秀基因，因为较差的基因也有可能更新出最优解
                if (Math.random() < 0.5) {
                    fit[i] = new_fit;
                    gene[i] = new_gene[i].clone();
                }
                x = decode(new_gene[i]);
            }
        }
    }

    /**
     * 生成最优解
     */
    private void generateOptimization() {
        // 获取最优值
        double optimalOutput = getInput().getFunction().apply(x);
        // 获取最优值时自变量取值
        double[] optimalInput = x.clone();
        setOutput(new Output(optimalOutput, optimalInput));
    }

    /**
     * 运行并计算结果
     */
    @Override
    public void go() {
        int t;
        for (t = 1; t < getIter() + 1; t++) {
            scan(t);
        }
        generateOptimization();
    }

    /**
     * 运行并计算结果（按迭代逐步跟踪），如果目的是计算出结果，请使用{@link #go()}
     *
     * @param author   作者
     * @param message  备注
     * @param title    标题
     * @param fileType 文件类型 {@link FileType}
     * @return {@link Tracker}
     */
    @Override
    public Tracker tracker(String author, String message, String title, FileType fileType) {
        int t;
        Tracker tracker = new Tracker(this, author, message, title, fileType);
        tracker.startTracker();
        for (t = 0; t < getIter(); t++) {
            scan(t);
            tracker.trackOne(t + 1);
        }
        generateOptimization();
        tracker.endTracker();
        return tracker;
    }

    /**
     * 生成报告
     *
     * @param author   作者
     * @param message  备注
     * @param title    标题
     * @param fileType 文件类型 {@link FileType}
     * @return {@link Report}
     */
    @Override
    public Report report(String author, String message, String title, FileType fileType) {
        return new Report(this, author, message, title, fileType);
    }

    /* Getter/Setter 部分*/
    public int getN() {
        return n;
    }
    public void setN(int n) {
        this.n = n;
    }
    public int getLength() {
        return length;
    }
    public void setLength(int length) {
        this.length = length;
    }

    /* Getter 部分*/

    public double getPc() {
        return pc;
    }
    public double getPm() {
        return pm;
    }
    public double[] getFit() {
        return fit;
    }
    public String[][] getGene() {
        return gene;
    }
    public double[] getX() {
        return x;
    }
}
